package com.base.doublepoint.slidingwindows;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 438. 找到字符串中所有字母异位词
 *给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
 *
 * 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author leon
 * @date 2021年11月28日 14:47
 */
public class FindAnagrams {
    public List<Integer> findAnagrams(String s, String p) {
        //差异性哈希表
        Map<Character,Integer> diffMap = new HashMap<>();
        for(int i = 0;i<p.length();i++){
            diffMap.put(p.charAt(i),diffMap.getOrDefault(p.charAt(i),0)+1);
        }
        List<Integer> res = new ArrayList<>();
        int start = 0;
        for(int end =0;end<s.length();end++){

            diffMap.put(s.charAt(end),diffMap.getOrDefault(s.charAt(end),0)-1);
            if(diffMap.get(s.charAt(end))==0){
                diffMap.remove(s.charAt(end));
            }

            if(end-start+1>=p.length()){

                if(diffMap.isEmpty()){
                    res.add(start);
                }
                diffMap.put(s.charAt(start),diffMap.getOrDefault(s.charAt(start),0)+1);
                if(diffMap.get(s.charAt(start))==0){
                    diffMap.remove(s.charAt(start));
                }
                start++;

            }
        }
        return res;
    }
}
